package 二叉树高频题目_上_不含树型dp;

import java.util.*;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal {

    // 定义树节点
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 提交时把方法名改为levelOrder，此方法为普通bfs，此题不推荐
    public List<List<Integer>> levelOrder1(TreeNode root) {
        // 最终结果
        List<List<Integer>> ans = new ArrayList<>();
        if(root != null){
            // 初始化队列
            Queue<TreeNode> queue = new LinkedList<>();
            // 初始化HashMap，k值为：TreNode节点，v值为：该节点在二叉树中的层数。从0开始
            HashMap<TreeNode, Integer> levels = new HashMap<>();
            queue.add(root);
            levels.put(root, 0);
            while(!queue.isEmpty()){
                TreeNode cur = queue.poll();
                // 当前弹出节点的层数
                int level = levels.get(cur);
                // 如果结果链表的大小和节点的层数相同，说明该节点还未在结果链表中初始化
                if(ans.size() == level){
                    ans.add(new ArrayList<>());
                }
                // 将该节点放入到相应层次的链表集合中
                ans.get(level).add(cur.val);
                if(cur.left != null){
                    queue.add(cur.left);
                    levels.put(cur.left, level+1);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                    levels.put(cur.right, level+1);
                }
            }
        }
        return ans;
    }

    // 使用数组来代替链表
    private static int MAXN = 2001;
    TreeNode[] queue = new TreeNode[MAXN];
    // 使用l和r来记录数组链表中的数据，是[l, r)
    private static int l, r;
    // 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 最终结果
        List<List<Integer>> ans = new ArrayList<>();
        if(root != null){
            // 初始化，[0, 1)
            l = r = 0;
            queue[r++] = root;
            while(l < r){//队列中还有东西
                // 二叉树当前层的节点个数
                int size = r - l;
                ArrayList<Integer> list = new ArrayList<>();
                // 每次处理二叉树一层的节点
                for(int i = 0; i < size; i++){
                    TreeNode cur = queue[l++];
                    list.add(cur.val);
                    if(cur.left != null){
                        queue[r++] = cur.left;
                    }
                    if(cur.right != null){
                        queue[r++] = cur.right;
                    }
                }
                ans.add(list);
            }
        }
        return ans;
    }
}
